package org.lql.algo.codecrush.hot100.substring;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: liangqinglong
 * @date: 2025-10-22 14:17
 * @description: 76. 最小覆盖子串 <a href="https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class MinWindow {

	public String minWindow(String s, String t) {
		// 统计字符串t中的字符频率
		Map<Character, Integer> need = new HashMap<>();
		for (char c : t.toCharArray()) {
			need.put(c, need.getOrDefault(c, 0) + 1);
		}
		// 统计当前窗口的字符
		Map<Character, Integer> window = new HashMap<>();
		// 窗口左右边界
		int left = 0;
		int right = 0;
		// 符合条件的字符
		int valid = 0;
		// 最小覆盖字符串的索引
		int start = 0;
		int minLen = Integer.MAX_VALUE;
		while (right < s.length()) {
			// 当前字符
			char current = s.charAt(right);
			// 扩大窗口
			right++;
			// 是否为目标字符
			if (need.containsKey(current)) {
				// 放入窗口
				window.put(current, window.getOrDefault(current, 0) + 1);
				// 判断字符频率
				if (window.get(current).intValue() == need.get(current).intValue()) {
					valid++;
				}
			}
			// 窗口左边界收缩
			while (valid == need.size()) {
				if (right - left < minLen) {
					start = left;
					minLen = right - left;
				}
				char leftSide = s.charAt(left);
				left++;
				if (need.containsKey(leftSide)) {
					if (window.get(leftSide).intValue() == need.get(leftSide).intValue()) {
						valid--;
					}
					window.put(leftSide, window.get(leftSide) - 1);
				}
			}
		}
		return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
	}

	public static void main(String[] args) {
		MinWindow minWindow = new MinWindow();
		System.out.println(minWindow.minWindow("ADOBECODEBANC", "ABC"));
		System.out.println(minWindow.minWindow("a", "a"));
		System.out.println(minWindow.minWindow("a", "aa"));
	}
}
